/*
题目描述
用筛选法求100之内的素数，并输出。

输入
无

输出
在一行中输出100之内的所有素数，在每个素数后输出一个空格。
请注意行尾输出换行。
*/
// 本代码使用欧拉筛算法实现
// 其他筛法还有埃拉托斯特尼筛法
// 可以自行搜索相关资料，了解这两种筛选法的原理与实现。
#include<stdio.h>

int main() {
    int n = 100;
    int primes[100];  // 存储素数的数组
    int isPrime[101] = {0};  // 标记数组，0表示素数，1表示合数
    int count = 0;  // 素数计数器
    
    // 欧拉筛算法
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) {
            primes[count++] = i;  // i是素数，加入素数数组
        }
        // 用当前素数primes[j]去筛掉合数
        for (int j = 0; j < count && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = 1;  // 标记为合数
            if (i % primes[j] == 0) {
                break;  // 关键步骤：保证每个合数只被最小质因子筛掉
            }
        }
    }
    
    // 输出结果
    for (int i = 0; i < count; i++) {
        printf("%d ", primes[i]);
    }
    printf("\n");
    
    return 0;
}